package algorithm.binaryTree;

import java.util.Stack;

public class balancedTreeByIterativeMethod {
    public static void main(String[] args) {
        TreeNode node7 = new TreeNode(7);
        TreeNode node15 = new TreeNode(15);
        TreeNode node20 = new TreeNode(20, node15, node7);
        TreeNode node9 = new TreeNode(9);
        TreeNode root = new TreeNode(3 , node9, node20);
        Calulate calulate = new Calulate();
        boolean b = calulate.isBalanced(root);
        System.out.println(b);
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static class Calulate{
        public boolean isBalanced(TreeNode root) {
            if(root == null) return true;
            //后序遍历：左右中
            //后序遍历（迭代法） ：用栈
            Stack<TreeNode> stack = new Stack<>();//初始化
            TreeNode prev = null;// 标记：被访问过的节点
            //遍历：只要未被遍历完这棵树（root不为空 或入栈的未处理完）
            while (root != null || !stack.isEmpty()){
                // 左：先一路向左入栈
                while (root != null){
                    stack.push(root);
                    root = root.left;
                }
                // 右：右节点不为空并且未被访问过，才能入栈遍历它（再次左右中，先左）
                //从栈顶节点（就是从最底层的最左的节点）开始遍历
                TreeNode node = stack.peek();
                if(node.right !=null && node.right != prev){
                    // 右结点还没遍历，遍历右结点
                    //stack.push(node.right);  //与下一行重复了
                    root = node.right; //使得root不为空，会在while循环里入栈
                }else {
                    //否则右节点空 || 被访问过， 当前节点已经被遍历过
                    //getHeight第一次传参：node是最底层的最左边的叶子节点，传入的node.left为null
                    if(Math.abs(getHeight(node.left) - getHeight(node.right)) > 1)
                        return false;// 不是高度平衡的二叉树(左右子树的高度差 >1)

                    // 中：当前节点已经被遍历过，就出栈
                    stack.pop();
                    root = null;//null表示不用再一路向左遍历了
                    prev = node;
                }
            }
            //全遍历都不出问题后
            return true;
        }

        //求高度的方法1：
        //优化迭代法，对暴力迭代法的方法做优化，
        // 利用TreeNode.val来保存当前结点的高度，这样就不会有重复遍历，
        // 使得获取高度算法时间复杂度可以降到O(1)，总的时间复杂度降为O(n)。
        private int getHeight(TreeNode root){
            // getHeight第1/2次：传入的root是叶子节点.left为null
            // 第3次参数：node是最底层的最左边的叶子节点，则node.left为null

            if(root == null) return 0;
            int leftHeight = root.left ==null? 0:root.left.val;
            int rightHeight = root.right == null? 0 : root.right.val;
            int height = Math.max(leftHeight,rightHeight) +1;
            //先保存当前节点的高度
            root.val = height;
            return height;
        }
    }

}
